＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　　　　　　 ■■■■
　　　　　■　　　　■　　　　　　　■　　　　　　　　■
　　　　　■　　　　　　　　　　　■■■　　　　　　■■■
　　　　　■　　　　■　　　　　　　■　　　　　　　　■
　　　　　　 ■■■■
               〜基礎から　★　Ｃ＋＋Ｐｒｏｇｒａｍｉｎｇ〜
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　　【注意】　このマガジンは、最大化してお読みください。
　　　　　　　また、等角フォントでお読みください。
　　　　　　　　　　（ＭＳ　ゴシックなど）

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

　発行者　　　　　　むーくん
　マガジンＮＯ．　　アルゴリズム編No.42 掃き出し法
　発行日　　　　　　02/08/12
　講読人数　　　　　３８００名ぐらい
　マガジンＩＤ　　　0000050494
　　　　　　　　　　このマガジンは、まぐまぐから配信されています。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★あいさつ★

夏休みも残すところあと２週間ほどとなって、
中学生や高校生の方は必死に宿題を写しているころでしょうか（笑）
のんきにメルマガを書いてられるので幸せといっちゃぁ幸せです。

そろそろこのアルゴリズム編も終盤にさしかかってきたので、
ラストスパートをかけようかと思ってます。
新たに読者になってくださったみなさんも、文法に関しては
追いついてくださったでしょうか？
しばらく本編はお休みしてますので・・・

久しぶりにメールチェックしたら、たくさん頂いてました。
これから一つ一つお返事しますので、ちょっと待ってくださいね ^^;

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★目次★

　　　・掃き出し法
　　　・アルゴリズム
　　　・サンプルプログラム
　　　・注意
　　　・今日のポイント
　　　・予告

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★掃き出し法の概要★

掃き出し法というのは、中学校で習う「加減法」に当たります。

連立方程式のある式を数倍し、他の式に足したり引いたりする方法です。
加減法では、計算のしやすさを考えて
どの式を何倍しても、どの変数から計算しても良かったのですが、
掃き出し法では、順序を厳密に定めてやります。
コンピュータはそちらの方が分かりやすいからです。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★アルゴリズム★

では、実際に例を示しながらやってみることにします。

　　｛ 3x + 2y +  z = 10
　　｛  x +  y + 2z = 9
　　｛ 2x + 3y +  z = 11

この連立方程式を解くことにします。
掃き出し法では、まず、一番最初にxの項を消去することから考えます。
その際、第一式のxの項を「ピボット数（軸数）」と呼ぶことにします。

第一式をピボット数の係数、3で割ります。すると

　　｛  x + 2/3 y + 1/3 z = 10/3
　　｛  x +  y + 2z = 9
　　｛ 2x + 3y +  z = 11

となります。

第一式を使って、第二式、第三式を消去することができます。
第一式を１倍して引いてやれば、第二式のxが、
第一式を２倍して引いてやれば、第三式のxが消去されます。

　　｛  x + 2/3 y + 1/3 z = 10/3
　　｛      1/3 y + 5/3 z = 17/3
　　｛      5/3 y + 1/3 z = 13/3

となります。
次に、yの項を消去することを考えます。
ここでは、第二式のyの項を「ピボット数」にします。

第二式のピボット数の係数、1/3で第二式を割ります。すると

　　｛  x + 2/3 y + 1/3 z = 10/3
　　｛          y + 5 z   = 17
　　｛      5/3 y + 1/3 z = 13/3

となります。

だんだん分かってきたと思いますが、第n式のn番目の項が
ピボット数になります。
ピボット数の係数でその式を割れば、ピボット数の係数を１にできます。
ということは、その式を数倍して足したり、引いたりするだけで
他の式の項を消去できるわけです。

では、この式を2/3倍して引いてやれば、第一式のyが
5/3倍して引いてやれば、第三式のyが消去されます。

　　｛  x      - 3 z = -8
　　｛       y + 5 z = 17
　　｛         - 8 z = -24

となります。

次は、第三式のピボット数、-8で第三式を割ります。

　　｛  x      - 3 z = -8
　　｛       y + 5 z = 17
　　｛             z = 3

第三式を-3倍して引いてやれば、第一式のzが
5倍して引いてやれば、第三式のzが消去されます。

　　｛  x          = 1
　　｛       y     = 2
　　｛           z = 3

こうして最後まで処理すると、x=1, y=2, z=3となっていることが
分かります。
このように、掃き出し法を使うと、決まった処理を繰り返すだけで
連立方程式を解くことが可能になります。


　◆掃き出し法のまとめ

　　・第一式をピボット数で割り、他の第一項を消去

　　　　　　　　↓

　　・第二式をピボット数で割り、他の第二項を消去

　　　　　　　　↓

　　・第ｎ式をピボット数で割り、他の第ｎ項を消去

　　　　　　　　↓

　　・残った定数項が解となる

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★サンプルプログラム★

掃き出し法を実現するプログラムを作成しなさい

#include<iostream>
using namespace std;

int main(){
    int dim, i, j, k;          /* カウンタ */
    double pivot,erase;        /* ピボット数、消去係数 */
    double** a;                /* 連立方程式の各係数 */
    
    cout << "連立方程式の未知数の個数は : ";   /* 次元数の入力 */
    cin >> dim;
    
    a = new double*[dim];                      /* メモリ確保 */
    for(i=0;i<dim;i++)a[i] = new double[dim+1];
    
    for(i=0;i<dim;i++){                        /* 係数入力部 */
        for(j=0;j<dim+1;j++){
            cout << "a[" << i << "][" << j << "] : ";
            cin >> a[i][j];
        }
    }
    
    for(i=0;i<dim;i++){                       /* 掃き出し部 */
        pivot = a[i][i];                      /* ピボット数を取得 */
        for(j=0;j<dim+1;j++) a[i][j]/=pivot;  /* n式をピボットで割る */
        for(k=0;k<dim;k++){                   /* n項を消去する */
            erase=a[k][i];                    /* 消去する式の係数 */
            for(j=i;j<dim+1;j++){             /* 実際の掃き出し処理 */
                if(k!=i) a[k][j]-=erase*a[i][j];
            }
        }
    }
    
    for(i=0;i<dim;i++){                    /* 結果表示(dim番目の数) */
        cout << "x[" << i << "] = " << a[i][dim] << endl;
    }
    return 0;
}

─[実行結果]──────────────────────────────

｛ 3x + 2y +  z = 10
｛  x +  y + 2z = 9
｛ 2x + 3y +  z = 11　　を解く

　　連立方程式の未知数の個数は : 3
　　a[0][0] : 3
　　a[0][1] : 2
　　a[0][2] : 1
　　a[0][3] : 10
　　a[1][0] : 1
　　a[1][1] : 1
　　a[1][2] : 2
　　a[1][3] : 9
　　a[2][0] : 2
　　a[2][1] : 3
　　a[2][2] : 1
　　a[2][3] : 11
　　x[0] = 1
　　x[1] = 2
　　x[2] = 3

─[解説]────────────────────────────────

まず、次元数を入力します。
もし、次元数が３ならば、３×４で、１２個の領域が必要です。
よって、まず、double** aに、double*型をdim個取得し、
その領域に、double型をdim+1個取得します。

つまり、dim行・dim+1列の２次元配列を取得しています。

　※このあたりのポインタ操作が分からない方は、バックナンバー170
　　http://mukun_mmg.tripod.co.jp/mmg/bncpp/170.html　などを
　　参照すると良いと思います

で、その領域に、係数を入力していきます。


掃き出し部では、上で解説したように、掃き出し処理を
行っていきます。
ここで、カウンタiは現在のピボット行、
カウンタjは列、カウンタkは消去される行を指しています。

最後に、各行のdim番目の数が結果になっているので
それを表示します。

────────────────────────────────────

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★注意★

ピボット数があまり小さくなりすぎた場合、
結果に誤差が生じることがあります。
なぜなら、微小数で割られることで、
式全体の値が大きくなりすぎるからです。

その場合、式の順序を入れ替えるとうまくいくことがあります。


また、今回のプログラムでは、解空間がゼロ次元のものしか
解くことができません。
例えば、
　　｛  x +  y = 2
　　｛ 2x + 2y = 4　などは強制終了されます。ご注意を。

　※解空間については、前回を参照してください

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★今日のポイント★

　　・掃き出し法とは、加減法の一種である

　　・掃き出し法のアルゴリズムは以下の通りである


　　　　第一式をピボット数で割り、他の第一項を消去
　　　　　　　　　　↓
　　　　第二式をピボット数で割り、他の第二項を消去
　　　　　　　　　　↓
　　　　第ｎ式をピボット数で割り、他の第ｎ項を消去
　　　　　　　　　　
　　　　　　　　残った定数項　：　解

　　・掃き出し法では、ピボット数が小さくなりすぎると
　　　うまくいかないことがある

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
★予告★

　　　ガウス・ザイデル法を学習します

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

講読解除はこちら
http://web1.freecom.ne.jp/~mu-home/mmg/cpp.html

バックナンバーはこちら
http://web1.freecom.ne.jp/~mu-home/mmg/cpp.html

内容について質問やご意見など
smukun.com

筆者のホームページ（むーくんの理学的なんでも講座）
http://www.hello.sh/nandemo/

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊